mod rc_linked_list;
mod d_link_list;

use std::mem;
// use std::slice::{Iter, IterMut};

fn main() {}

#[derive(Debug, Clone)]
pub struct Node<T> {
    elem: T,
    next: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

#[derive(Debug, Clone)]
pub struct List<T> {
    head: Link<T>,
}


// 实现Drop 销毁对象的时候才调用
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        loop {
            let mut curr = self.head.take();
            match curr {
                Link::None => return,
                Link::Some(node) => {
                    self.head = node.next;
                }
            }
        }
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: Link::None }
    }

    //  取出头部元素
    pub fn pop(&mut self) -> Option<T> {

        // option 的 take 方法是取出 其中的元素
        let node = self.head.take();

        match node {
            Link::None => None,
            Link::Some(node) => {
                // 将head 指向下一个元素
                self.head = node.next;
                Some(node.elem)
            }
        }
    }


    // 取出头部的值
    pub fn peek(&self) -> Option<&T> {
        match &self.head {
            Link::None => None,
            Link::Some(node) => Some(&node.elem),
        }
    }


    // 返回一个可以修改头部引用
    pub fn peek_mut(&mut self) -> Option<&mut T> {
        match &mut self.head {
            Link::None => None,
            Link::Some(ref mut node) => Some(&mut node.elem),
        }
    }


    // 插入到头部
    pub fn push(&mut self, elem: T) {
        // replace<T>(dest: &mut T, src: T)     是  dest 和 src 交换， 然后 返回 dest

        // self.head.take() 等价于  mem::replace(&mut self.head, Link::None)

        // 这一句相当于下面三句
        let node = Box::new(Node { elem: elem, next: self.head.take() });

        /*let head = &self.head;
        let node = Box::new(Node { elem: elem, next: (*head).clone() });
        self.head = Link::None;*/

        self.head = Link::Some(node);
    }
}


//  rust 应该实现 3中迭代器
// IntoIter - T
// IterMut - &mut T
// Iter - &T
// 这3中迭代器的区别是 : IntoIter 类型迭代器的 next 方法会拿走被迭代值的所有权，IterMut 是可变借用， Iter 是不可变借用


//  next 方法会拿走被迭代值的所有权
pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

// ---------------------Iter   拿到的是引用-----------------------------

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}


impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            // Converts from Option<T> (or &Option<T>) to Option<&T::Target>.
            let temp = node.next.as_deref();
            self.next = temp;

            &node.elem
        })
    }
}


impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter {
            // Converts from Option<T> (or &Option<T>) to Option<&T::Target>.
            next: self.head.as_deref()
        }
    }
}


// ------------------IterMut  ------------------------------

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}


impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_deref_mut();
            //
            &mut node.elem
        })
    }
}


impl<T> List<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            // Converts from Option<T> (or &mut Option<T>) to Option<&mut T::Target>.
            next: self.head.as_deref_mut()
        }
    }
}


#[cfg(test)]
mod test {
    use crate::List;


    #[test]
    fn test1() {
        let mut op1 = Some(1);
        assert_eq!(op1.take(), Some(1));
        assert_eq!(op1.take(), None);
    }


    #[test]
    fn test_list_i32() {
        let mut list = List::new();

        list.push(2);
        list.push(1);

        let node = list.pop();
        println!("node is {:?}  list is {:?}", node, list);

        let node = list.pop();
        println!("node is {:?}  list is {:?}", node, list);

        let node = list.pop();
        println!("node is {:?}  list is {:?}", node, list);

        println!("list is {:?}", list);
    }

    #[test]
    fn test_list_str() {
        println!("Hello, world!");
        let mut list = List::new();

        list.push("node1");
        list.push("node2");

        assert_eq!(list.pop(), Some("node2"));

        assert_eq!(list.pop(), Some("node1"));
        assert_eq!(list.pop(), None);
    }


    #[test]
    fn test_peek() {
        let mut list = List::new();

        assert_eq!(list.peek(), None);
        list.push("1".to_string());
        list.push("2".to_string());
        list.push("3".to_string());

        println!("{:?}", list);

        let node = list.peek().unwrap();

        println!("node is {:?}", node);
        println!("after peek  list is  {:?}", list);

        let node = list.pop().unwrap();
        println!("node is {:?}", node);
        println!("after pop  list is  {:?}", list);
    }


    #[test]
    fn test_peek_mut() {
        let mut list = List::new();

        assert_eq!(list.peek(), None);
        list.push("1".to_string());
        list.push("2".to_string());
        list.push("3".to_string());


        println!("list is {:?}", list);
        let mut node_mut = list.peek_mut().unwrap();


        // * 是解引用
        *node_mut = String::from("aaaa");


        println!("after modify list is {:?}", list);
    }


    //   3个迭代器的测试用例

    #[test]
    fn test_into_iter() {
        let mut list = List::new();

        list.push(1);
        list.push(2);
        list.push(3);
        list.push(4);


        let mut iter = list.clone().into_iter();

        assert_eq!(iter.next(), Some(4));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), None);
    }


    #[test]
    fn test_iter() {
        let mut list = List::new();

        list.push(1);
        list.push(2);
        list.push(3);
        list.push(4);


        let mut iter = list.iter();


        assert_eq!(iter.next(), Some(&4));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), None);
    }


    #[test]
    fn test_iter_mut() {
        let mut list = List::new();

        list.push(1);
        list.push(2);
        list.push(3);
        list.push(4);


        let mut iter_mut = list.iter_mut();

        assert_eq!(iter_mut.next(), Some(&mut 4));
        assert_eq!(iter_mut.next(), Some(&mut 3));
        assert_eq!(iter_mut.next(), Some(&mut 2));
        assert_eq!(iter_mut.next(), Some(&mut 1));
        assert_eq!(iter_mut.next(), None);
    }
}